//
//  TwoSum.swift
//  LeetCodeSummary
//
//  Created by WangYonghe on 2020/5/8.
//  Copyright © 2020 WangYonghe. All rights reserved.
//  1：两数之和

import UIKit

/*
 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

 示例:
    给定 nums = [2, 7, 11, 15], target = 9

    因为 nums[0] + nums[1] = 2 + 7 = 9
    所以返回 [0, 1]

 来源：力扣（LeetCode）
 链接：https://leetcode-cn.com/problems/two-sum
 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

class TwoSum: NSObject {
    
    func twoSumResult(nums: [Int], target: Int)->Array<Int>{
        
        var dict = [Int:Int]()
        for (i,num) in nums.enumerated() {
            if let lastIndex = dict[target - num] {
                return [lastIndex ,i]
            }else{
                dict[2] = 0
                dict[num] = i
            }
        }
        return []
    }
    
    
    //简化版本  只需判断是否存在两个数相加等于目标值
    func twoSumSimple(nums: [Int], target: Int)->Bool{
  
        var tmpArr:[Int] = []
        
        for element:Int in nums{
            if tmpArr.contains(target - element) {
                return true
            }else{
                tmpArr.append(element)
            }
        }
        
        return false
    }
    
    
    
    

    /*
     167. 两数之和 II - 输入有序数组
     给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。

     函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。

     说明:

     返回的下标值（index1 和 index2）不是从零开始的。
     你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
     示例:

     输入: numbers = [2, 7, 11, 15], target = 9
     输出: [1,2]
     解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
     */
    func twoSumSoredArr(_ numbers: [Int], _ target: Int) -> [Int] {
        //暴力解法  该解法耗时2360ms
        var point1 = 0
        var point2 = 1
        while point1 < point2 && point2 < numbers.count {
            let sum = numbers[point1] + numbers[point2]
            if sum == target{
                return [point1+1,point2+1]
            }else if sum > target{
                point1 += 1
                point2 = point1 + 1
            }else if sum < target{
                if point2 == numbers.count - 1 {
                    point1 += 1
                    point2 = point1 + 1
                }else{
                    point2 += 1
                }
            }
        }
        return [0,0]
    }
    
    func twoSumSoredArr2(_ numbers: [Int], _ target: Int) -> [Int] {
        //双指针法 从数组的两端往中间进行查找  该解法耗时40ms
        var point1 = 0
        var point2 = numbers.count-1
        while point1 < point2{
            let sum = numbers[point1] + numbers[point2]
            if sum == target{
                return [point1+1,point2+1]
            }else if sum > target{
                point2 -= 1
            }else if sum < target{
                point1 += 1
            }
        }
        return [0,0]
    }
    
    func twoSumSoredArr3(_ numbers: [Int], _ target: Int) -> [Int] {
        //二分法   耗时48ms
        for i in 0 ... numbers.count - 1 {
            var left = i+1
            var right = numbers.count-1
            
            while left <= right {
                let mid = left + (right-left)/2
                if numbers[i] + numbers[mid] == target{
                    return [i+1,mid+1]
                }else if numbers[i] + numbers[mid] < target{
                    left = mid+1
                }else if numbers[i] + numbers[mid] > target{
                    right = mid-1
                }
            }
        }
        return [0,0]
    }
}



